/*
264. Ugly Number II
Total Accepted: 31536 Total Submissions: 110242 Difficulty: Medium

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number. 

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Subscribe to see which companies asked this question

*/

class Solution {
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

#define inster_num(c, m, q, count, n)\
    if (count < n){ q.push(c);if(c > m)m=c;count++;}\
    else if (c < m){q.push(c);m=c;}
public:
    int nthUglyNumber(int n) {
        static ListNode *head(1);
        static ListNode *cur = head;
        static 
        while(!pv.empty()){
            int cur = pv.front();
            pv.pop();
            if (cur > max) continue;

            // is pow of 2
            if ((cur & (cur -1)) == 0){
                inster_num(cur *2, max, pv, count, n);
                inster_num(cur *3, max, pv, count, n);
                inster_num(cur *5, max, pv, count, n);
            } else if ((cur %5) != 0){ // has no 5 in thiz number
                inster_num(cur *3, max, pv, count, n);
                inster_num(cur *5, max, pv, count, n);
            } else {
                inster_num(cur *5, max, pv, count, n);
            }
        }
        return max;
    }
};


class Solution {
public:
    int min(int a, int b) {
        return a < b ? a:b;
    }
    
    int min(int a, int b, int c) {
        return min( min(a, b),  c);
    }
    int nthUglyNumber(int n) {
            
        static int i=0, j=0, k=0;
        static vector<int> v(1,1);
    
        if (v.size()>=n) return v[n-1];
        
        while(v.size() < n){
            int next = min(v[i]*2, v[j]*3, v[k]*5);
            if (next == v[i]*2) i++;
            if (next == v[j]*3) j++;
            if (next == v[k]*5) k++;
            v.push_back(next);
        }
        return v.back();
    }

};

